import io
import tokenize

class Lexer(object):
    def __init__(self, src_path):
        self.f = open(src_path)
        self.lex = tokenize.generate_tokens(self.f.readline)
        self.cur = None

    def get_next(self):
        # if self.cur is not None and self.cur.type == tokenize.ENDMARKER:
        #     return None
        if self.cur is None:
            self.cur = next(self.lex)
            # print(self.cur)
        return self.cur

    def report_err(self, msg):
        print(msg)
        exit()

    def match(self, tocken_type):
        if self.cur is None:
            self.report_err("")
        if self.cur.type != tocken_type:
            self.report_err("Error: expected %s, but got %s at %s" % (self.cur.type, tocken_type, self.cur))
        pre = self.cur
        self.cur = next(self.lex)
        return pre

    def print_all(self):
        tmp = self.get_next()
        while tmp.type != tokenize.ENDMARKER:
            print(tmp)
            self.cur = None
            tmp = self.get_next()


class Node:
    def accept(self, visitor):
        pass

class VoidNode(Node):
    def accept(self, visitor):
        visitor.visit_void_node(self)


class NumberNode(Node):
    def __init__(self, val_token):
        self.val_tk = val_token
        self.val = int(val_token.string)

    def accept(self, visitor):
        visitor.visit_number_node(self)

    def __str__(self):
        return self.val_tk.string


class OpNode(Node):
    def __init__(self, left_node, right_node, op_t):
        self.left = left_node
        self.right = right_node
        self.tocken = op_t
        self.op_str = op_t.string

    def accept(self, visitor):
        visitor.visit_op_node(self)

    def __str__(self):
        return '"' + self.op_str + '"'

class BracketsNode(Node):  # 用于括号类型 Parentheses( )
    def __init__(self, inner_node, paren_l_t, paren_r_t):
        self.inner_node = inner_node
        self.l_str = paren_l_t.string
        self.r_str = paren_r_t.string

    def accept(self, visitor):
        visitor.visit_brackets_node(self)

    def __str__(self):
        return '"' + self.l_str + " " + self.r_str + '"'

class ListNode(Node):
    def __init__(self):
        self.node_lst = list()

    def append(self, n):
        self.node_lst.append(n)

    def accept(self, visitor):
        visitor.visit_list_node(self)


class Parser:
    def __init__(self, src_path):
        self.lexer = Lexer(src_path)
        self.err_list = list()

    def print_error(self):
        for i in self.err_list:
            print(i)

    def statements_list(self):
        list_node = ListNode()
        t = self.lexer.get_next()
        while t.type != tokenize.ENDMARKER:
            n = self.statement()
            list_node.append(n)
            t = self.lexer.get_next()
            while t.type == tokenize.NEWLINE:
                self.lexer.match(tokenize.NEWLINE)
                t = self.lexer.get_next()
        return list_node

    def statement(self):
        t = self.lexer.get_next()
        if t.type == tokenize.ENDMARKER:
            return VoidNode()
        if t.type == tokenize.NUMBER or t.type == tokenize.OP:
            return self.expr()
        self.err_list.append("Unexcept tocken: %s" % str(t))
        return VoidNode()

    def term(self):
        left = self.factor()
        while True:
            op = self.lexer.get_next()
            if op.type != tokenize.OP or op.string not in ('*', '/'):
                break
            self.lexer.match(tokenize.OP)
            right = self.factor()
            left = OpNode(left, right, op)  # 左结合乘除
        return left

    def expr(self):
        left = self.term()
        while True:
            op = self.lexer.get_next()
            if op.type != tokenize.OP or op.string not in ('+', '-'):
                break
            self.lexer.match(tokenize.OP)
            right = self.term()
            left = OpNode(left, right, op)  # 左结合加减
        return left

    def factor(self):
        token = self.lexer.get_next()
        if token.type == tokenize.OP and token.string == '(':
            self.lexer.match(tokenize.OP)  # 消耗左括号
            node = self.expr()  # 递归解析括号内表达式
            right_bracket = self.lexer.get_next()
            self.lexer.match(tokenize.OP)  # 消耗右括号
            if right_bracket.type != tokenize.OP and right_bracket.string != ')':
                self.err_list.append('Error: expect ")" but get: %s' % str(right_bracket))
            return BracketsNode(node, token, right_bracket)
        else:
            v = self.lexer.match(tokenize.NUMBER)
            return NumberNode(v)

class CalcVisitor:
    def __init__(self):
        self.ret_list = list()
        self.val = 0

    def visit(self, n: Node):
        n.accept(self)

    def visit_list_node(self, n: ListNode):
        for e in n.node_lst:
            self.visit(e)
            self.ret_list.append(self.val)
            print(self.val)

    def visit_number_node(self, n: NumberNode):
        self.val = n.val

    def visit_brackets_node(self, n: BracketsNode):
        self.visit(n.inner_node)

    def visit_op_node(self, n: OpNode):
        self.visit(n.left)
        left = self.val
        self.visit(n.right)
        right = self.val

        if n.op_str == "+":
            self.val = left + right
        elif n.op_str == "-":
            self.val = left + (-right)
        elif n.op_str == "*":
            self.val = left * right
        elif n.op_str == "/":
            self.val = left // right
        else:
            print("Error: unsupported op: ", n.op_str)

class AstPrintNode:
    node_id_cnt = 0  # 用于生成id

    def __init__(self, val):
        self.id = AstPrintNode.node_id_cnt
        AstPrintNode.node_id_cnt += 1
        self.val = val

    def __str__(self):
        return str(self.id) + '[' + str(self.val) + ']'

class AstGraphMarkdownLine:
    def __init__(self, l: AstPrintNode, r: AstPrintNode):
        self.left = l
        self.right = r

    def __str__(self):
        return str(self.left) + '-->' + str(self.right)

class SubAst:
    def __init__(self, statement, ast_graph_line_lst):
        self.statement = statement
        self.ast_graph = list()
        self.ast_graph += ast_graph_line_lst

    def __str__(self):
        return self.statement

    def get_ast_info(self):
        ret = self.statement + '\n'
        ret += '```mermaid\ngraph TD\n'
        for i in self.ast_graph:
            ret += str(i) + '\n'
        ret += '```\n'
        return ret

class PrintVisitor:
    def __init__(self):
        self.total_val_list = list()  # 用于记录遍历到了哪些node的字符类型值, 这个连起来将完整还原表达式
        self.ast_graph_line_lst_tmp = list()  # 用于存放当前语句的打印图信息
        self.ast_print_node_visit_tmp = list()  # 用于递归时记录当前在遍历到那一层节点了
        self.ret_list = list()  # 用于记录全程序的打印图信息
        self.sub_ast_info_list = list()  # 用于记录每条语句子ast的打印信息

    def print_ret(self):
        for s in self.sub_ast_info_list:
            print(s.get_ast_info())
        ret = '```mermaid\ngraph TD\n'
        for r in self.ret_list:
            ret += str(r) + '\n'
        ret += '```\n'
        print(ret)

    def visit(self, n: Node):
        n.accept(self)

    def visit_list_node(self, n: ListNode):
        root = AstPrintNode(" ")
        self.ast_print_node_visit_tmp.append(root)
        for e in n.node_lst:
            self.visit(e)
            curr_stmt = ' '.join(self.total_val_list)
            self.sub_ast_info_list.append(SubAst(curr_stmt, self.ast_graph_line_lst_tmp))
            # self.ast_graph_line_lst_tmp.append(AstGraphMarkdownLine(root, self.top_node))
            self.ret_list += self.ast_graph_line_lst_tmp
            self.ast_graph_line_lst_tmp.clear()
            self.total_val_list.clear()
            # print(self.val)

    def visit_number_node(self, n: NumberNode):
        self.ast_graph_line_lst_tmp.append(AstGraphMarkdownLine(self.ast_print_node_visit_tmp[-1], AstPrintNode(str(n))))
        self.total_val_list.append(n.val_tk.string)

    def visit_brackets_node(self, n: BracketsNode):
        self.total_val_list.append(n.l_str)
        brackets_print_node = AstPrintNode(str(n))
        self.ast_graph_line_lst_tmp.append(AstGraphMarkdownLine(self.ast_print_node_visit_tmp[-1], brackets_print_node))
        self.ast_print_node_visit_tmp.append(brackets_print_node)
        self.visit(n.inner_node)
        self.total_val_list.append(n.r_str)
        self.ast_print_node_visit_tmp.remove(brackets_print_node)

    def visit_op_node(self, n: OpNode):
        curr_op_print_node = AstPrintNode(str(n))
        self.ast_graph_line_lst_tmp.append(AstGraphMarkdownLine(self.ast_print_node_visit_tmp[-1], curr_op_print_node))
        self.ast_print_node_visit_tmp.append(curr_op_print_node)
        self.visit(n.left)
        self.total_val_list.append(n.op_str)
        self.visit(n.right)
        self.ast_print_node_visit_tmp.remove(curr_op_print_node)


if __name__ == '__main__':
    # lexer = Lexer("expr.txt")
    # lexer.print_all()
    p = Parser("expr.txt")
    # # print(p.lexer.get_next())
    lst_nd = p.statements_list()
    p.print_error()
    CalcVisitor().visit(lst_nd)
    print_ast = PrintVisitor()
    print_ast.visit(lst_nd)
    print_ast.print_ret()
